Collision Resolution Techniques (Chaining, Open Addressing)

Hashing হল ডাটা স্টোর করার একটি জনপ্রিয় প্রযুক্তি, যা দ্রুত অ্যাক্সেস এবং খোঁজার সুবিধা প্রদান করে। তবে, যখন দুটি বা ততোধিক ডেটা একই হ্যাশ ভ্যালু (ডেটাবেসের সূচক) পায়, তখন এটি একটি collision সৃষ্টি করে। হ্যাশ কনফ্লিক্ট বা collision সমাধান করতে দুইটি জনপ্রিয় পদ্ধতি হল: Chaining এবং Open Addressing।

এই টিউটোরিয়ালে, আমরা Collision Resolution Techniques যেমন Chaining এবং Open Addressing এর মাধ্যমে হ্যাশিংয়ের সমস্যা সমাধান করার পদ্ধতি দেখব এবং Java তে এগুলো কিভাবে ব্যবহার করা হয় তা ব্যাখ্যা করব।

1. Chaining

Chaining হল একটি collision resolution technique যেখানে একটি হ্যাশ টেবিলের প্রতিটি সূচকে একটি linked list বা অন্য কোন ডাটা স্ট্রাকচার (যেমন Queue) সংরক্ষিত থাকে। যখন একাধিক উপাদান একই সূচকে ম্যাপ হয়, তখন তারা একটি লিঙ্কড লিস্টের মতো যুক্ত হয়। এই পদ্ধতিতে ডেটা সংরক্ষণ করতে অনেক বেশি পরিমাণ মেমরি ব্যবহৃত হয়, তবে এটি খুবই কার্যকরী যখন কনফ্লিক্টের হার বেশি থাকে।

উদাহরণ: Chaining (Linked List)

import java.util.LinkedList;

class HashTable {
    // Array of LinkedLists to store elements
    private LinkedList<Integer>[] table;

    public HashTable(int size) {
        table = new LinkedList[size];
        for (int i = 0; i < size; i++) {
            table[i] = new LinkedList<>();
        }
    }

    // Hash function to map values to indices
    private int hashFunction(int key) {
        return key % table.length;
    }

    // Insert element into the hash table
    public void insert(int key) {
        int index = hashFunction(key);
        table[index].add(key); // Adding key to the corresponding linked list
    }

    // Search for an element in the hash table
    public boolean search(int key) {
        int index = hashFunction(key);
        return table[index].contains(key); // Search in the linked list
    }

    // Display the hash table
    public void display() {
        for (int i = 0; i < table.length; i++) {
            System.out.print(i + ": ");
            for (Integer key : table[i]) {
                System.out.print(key + " ");
            }
            System.out.println();
        }
    }
}

public class ChainingExample {
    public static void main(String[] args) {
        HashTable hashTable = new HashTable(7);

        // Inserting values
        hashTable.insert(10);
        hashTable.insert(20);
        hashTable.insert(15);
        hashTable.insert(25);
        hashTable.insert(30);

        // Display hash table
        hashTable.display();

        // Search for a value
        System.out.println("Search for 15: " + hashTable.search(15)); // Output: true
        System.out.println("Search for 40: " + hashTable.search(40)); // Output: false
    }
}

ব্যাখ্যা:

• Hash Table: একটি হ্যাশ টেবিল তৈরি করা হয় যেখানে প্রতিটি সূচকে একটি LinkedList রয়েছে।
• Hash Function: কীগুলিকে একটি সূচকে ম্যাপ করার জন্য একটি সাদাসিধে হ্যাশ ফাংশন ব্যবহার করা হয়।
• Insertion: একটি নতুন কীগুলি তার হ্যাশ সূচকে যুক্ত হয়।
• Search: হ্যাশ টেবিলের প্রতিটি সূচকের জন্য একটি লিঙ্কড লিস্ট ব্যবহার করে অনুসন্ধান করা হয়।

আউটপুট:

0: 
1: 15
2: 20
3: 10 
4: 
5: 25 
6: 30 
Search for 15: true
Search for 40: false

2. Open Addressing

Open Addressing একটি collision resolution technique যেখানে যদি দুটি উপাদান একই সূচকে ম্যাপ হয়, তবে এটি টেবিলের মধ্যে অন্য একটি খালি স্থানে ঐ উপাদানটি রাখে। এর মধ্যে কিছু জনপ্রিয় পদ্ধতি রয়েছে:

1. Linear Probing: পরবর্তী সূচকটি পরীক্ষা করে খালি পাওয়া গেলে উপাদানটি সেখানে সন্নিবেশ করা হয়।
2. Quadratic Probing: পরবর্তী সূচকটি কিছু নির্দিষ্ট ধাপে ধাপে পরীক্ষা করা হয়।
3. Double Hashing: দুটি হ্যাশ ফাংশন ব্যবহার করা হয়, প্রথমটি প্রাথমিক সূচক নির্ধারণ করে এবং দ্বিতীয়টি কনফ্লিক্ট হওয়া সূচকগুলিকে সমাধান করে।

উদাহরণ: Open Addressing (Linear Probing)

class HashTableOpenAddressing {
    private Integer[] table;
    private int size;

    public HashTableOpenAddressing(int size) {
        this.size = size;
        table = new Integer[size];
    }

    // Hash function
    private int hashFunction(int key) {
        return key % size;
    }

    // Insert element using linear probing
    public void insert(int key) {
        int index = hashFunction(key);

        // Linear probing to find an empty slot
        while (table[index] != null) {
            index = (index + 1) % size;
        }

        table[index] = key;
    }

    // Search for an element
    public boolean search(int key) {
        int index = hashFunction(key);

        while (table[index] != null) {
            if (table[index] == key) {
                return true;
            }
            index = (index + 1) % size;
        }

        return false;
    }

    // Display the hash table
    public void display() {
        for (int i = 0; i < size; i++) {
            System.out.print(i + ": ");
            if (table[i] != null) {
                System.out.print(table[i]);
            }
            System.out.println();
        }
    }
}

public class OpenAddressingExample {
    public static void main(String[] args) {
        HashTableOpenAddressing hashTable = new HashTableOpenAddressing(7);

        // Inserting values
        hashTable.insert(10);
        hashTable.insert(20);
        hashTable.insert(15);
        hashTable.insert(25);
        hashTable.insert(30);

        // Display hash table
        hashTable.display();

        // Search for a value
        System.out.println("Search for 15: " + hashTable.search(15)); // Output: true
        System.out.println("Search for 40: " + hashTable.search(40)); // Output: false
    }
}

ব্যাখ্যা:

• Hash Table: এখানে একটি সাদাসিধে হ্যাশ টেবিল ব্যবহার করা হয়েছে, যেখানে Open Addressing ব্যবহার করে কনফ্লিক্ট সমাধান করা হয়।
• Linear Probing: যদি সূচকটি খালি না থাকে, তবে পরবর্তী সূচকটি পরীক্ষা করা হয় এবং চলতে থাকে যতক্ষণ না খালি স্থানে পৌঁছায়।
• Insertion: নতুন কীগুলি প্রথমে হ্যাশ ফাংশন ব্যবহার করে ম্যাপ হয় এবং পরবর্তী খালি স্থানে প্রবাহিত হয়।

আউটপুট:

0: 10
1: 20
2: 15
3: 25
4: 30
5: 
6: 
Search for 15: true
Search for 40: false

3. Comparison Between Chaining and Open Addressing

সারাংশ

Collision Resolution techniques, such as Chaining and Open Addressing, are essential to ensure that hash functions handle conflicts efficiently.

• Chaining is simpler and often preferred when the number of collisions is high, as it allows the use of linked lists to manage collisions.
• Open Addressing, particularly Linear Probing, is more memory efficient but can degrade in performance when the hash table is nearly full.

Both methods have their advantages and are chosen based on the specific use case. Java provides the flexibility to implement both techniques effectively for efficient data storage and retrieval.